package P2分治回溯;

import java.util.LinkedList;

public class Maze {
    private static int[][] maze = {
            {1, 1, 1, 1, 1, 1, 1, 1, 1},
            {0, 0, 1, 0, 0, 0, 1, 1, 1},
            {1, 0, 1, 1, 1, 0, 1, 1, 1},
            {1, 0, 0, 0, 0, 0, 1, 1, 1},
            {1, 1, 0, 1, 1, 0, 0, 0, 1},
            {1, 0, 0, 0, 0, 0, 1, 0, 1},
            {1, 0, 1, 0, 1, 0, 0, 0, 1},
            {1, 1, 0, 0, 0, 0, 1, 0, 0},
            {1, 1, 1, 1, 1, 1, 1, 1, 1}
    };
    private static boolean[][] visted = new boolean[9][9];
    private static int enterX = 1, enterY = 0;
    private static int exitX = 7, exitY = 8;
    private static int[][] direction = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private static LinkedList<String> stack = new LinkedList<>();

    public static void main(String[] args) {
//        boolean flag = go(enterX, enterY);
//        if (flag) {
//            System.out.println("通了");
//            for (int i = stack.size() - 1; i >= 0; i--) {
//                System.out.println(stack.get(i));
//            }
//        } else {
//            System.out.println("无解");
//        }
        stack.clear();
        goUpper(enterX, enterY);
        System.out.println(stack);
    }

    private static void goUpper(int x, int y) {
        stack.push("(" + x + "," + y + ")");
        visted[x][y] = true;
        if (x == exitX && y == exitY) {
            System.out.println(stack);
            visted[x][y] = false;
            stack.pop();
            return;
        }
        for (int i = 0; i < direction.length; i++) {
            int nx = x + direction[i][0];
            int ny = y + direction[i][1];
            if (isInArea(nx, ny) && isRoad(nx, ny) && !visted[nx][ny]) {
                goUpper(nx, ny);
            }
        }
        visted[x][y] = false;
        stack.pop();
    }

    private static boolean go(int x, int y) {
        stack.push("(" + x + "," + y + ")");
        visted[x][y] = true;
        if (x == exitX && y == exitY) {
            return true;
        }
        for (int i = 0; i < direction.length; i++) {
            int nx = x + direction[i][0];
            int ny = y + direction[i][1];
            if (isInArea(nx, ny) && isRoad(nx, ny) && !visted[nx][ny]) {
                if (go(nx, ny)) {
                    return true;
                }
            }
        }
        stack.pop();
        return false;
    }

    private static boolean isInArea(int nx, int ny) {
        return 0 <= nx && nx < 9 && 0 <= ny && ny < 9;
    }

    private static boolean isRoad(int nx, int ny) {
        return maze[nx][ny] == 0;
    }
}